package math;

import java.util.Arrays;

import org.junit.Test;

public class Ex338 {
    class Solution {
        public int[] countBits1(int num) {
            int[] res = new int[num + 1];
            for (int i = 0; i <= num; i++) {
                res[i] = getOneNumber(i);
            }
            return res;
        }

        public int getOneNumber(int n) {
            int c = 0;
            while (n != 0) {
                if ((n & 1) == 1) c++;
                n >>>= 1;
            }
            return c;
        }

        public int[] countBits(int num) {
            int[] res = new int[num + 1];
            for (int i = 0; i <= num; i++) {
                if ((i & 1) == 1) {
                    res[i] = res[i - 1] + 1;
                } else {
                    res[i] = res[i >> 1];
                }
            }
            return res;
        }

    }

    @Test
    public void test() {
        Solution s = new Solution();
        System.out.println(Arrays.toString(s.countBits(100)));
        System.out.println(Arrays.toString(s.countBits1(100)));

    }

}
